package com.hardy.leecode;

import com.hardy.leecode.model.ListNode;

import java.util.HashSet;

/**
 * Author: Hardy
 * Date:   2020/6/26
 * Description:
 * - 面试题 02.01 移除重复节点
 * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
 *
 * 示例1:
 *
 *  输入：[1, 2, 3, 3, 2, 1]
 *  输出：[1, 2, 3]
 * 示例2:
 *
 *  输入：[1, 1, 1, 1, 2]
 *  输出：[1, 2]
 * 提示：
 *
 * 链表长度在[0, 20000]范围内。
 * 链表元素在[0, 20000]范围内。
 * 进阶：
 *
 * 如果不得使用临时缓冲区，该怎么解决？
 *
 * 链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
 **/
public class Que0201 {
    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 3, 2, 1};

        ListNode head = ListNode.gen(a);

        System.out.println(new Solution2().removeDuplicateNodes(head));
    }

    // 应用cache
    static class Solution1 {
        public ListNode removeDuplicateNodes(ListNode head) {
            if (head == null) return null;

            HashSet<Integer> cache = new HashSet<>();

            ListNode node = head;
            cache.add(node.val);

            while (node.next != null) {
                ListNode next = node.next;

                if (cache.contains(next.val)) {
                    node.next = next.next;
                } else {
                    cache.add(next.val);
                    node = next;
                }
            }
            return head;
        }
    }

    // 双指针
    static class Solution2 {
        public ListNode removeDuplicateNodes(ListNode head) {
            if (head == null) return null;

            ListNode node = head;

            while (node != null) {
                ListNode nodeAf = node;

                while (nodeAf.next != null) {
                    if (nodeAf.next.val == node.val)
                        nodeAf.next = nodeAf.next.next; // 跳过相同
                    else
                        nodeAf = nodeAf.next;
                }
                node = node.next;
            }
            return head;
        }
    }
}
